前缀和 & 差分

前缀和

定义

前缀和可以简单理解为「数列的前 $n$ 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。¹

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

例题

例题

有 $N$ 个正整数放到数组 $A$ 里，现在要求一个新的数组 $B$，新数组的第 $i$ 个数 $B[i]$ 是原数组 $A$ 第 $0$ 到第 $i$ 个数的和。

输入：

5
1 2 3 4 5

输出：

1 3 6 10 15

解题思路

递推：B[0] = A[0]，对于 $i \ge 1$ 则 B[i] = B[i-1] + A[i]。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组，相当于上文的 sum[]

int main() {
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      b[i][j] =
          b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和
    }
  }

  int ans = 0;

  int l = 1;
  while (l <= min(n, m)) {  // 判断条件
    for (int i = l; i <= n; i++) {
      for (int j = l; j <= m; j++) {
        if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
          ans = max(ans, l);  // 在这里统计答案
        }
      }
    }
    l++;
  }

  cout << ans << endl;
  return 0;
}

二维/多维前缀和

常见的多维前缀和的求解方法有两种。

基于容斥原理

这种方法多用于二维前缀和的情形。给定大小为 $m\times n$ 的二维数组 $A$，要求出其前缀和 $S$。那么，$S$ 同样是大小为 $m\times n$ 的二维数组，且

$$S_{i,j} = \sum_{i'\le i}\sum_{j'\le j}A_{i',j'}.$$

类比一维的情形，$S_{i,j}$ 可以基于 $S_{i-1,j}$ 或 $S_{i,j-1}$ 计算，从而避免重复计算；但直接相加会重复计算 $S_{i-1,j-1}$，因此需要将其减掉。由此得到递推关系：

$$S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}.$$

实现时，直接遍历 $(i,j)$ 求和即可。

示例

考虑一个具体的例子。

这里，$S_{3,3}$ 是左图中虚线方框内子矩阵的和。注意到 $S_{3,2}$ 和 $S_{2,3}$ 分别为蓝色和红色子矩阵的和，但它们的重叠部分 $S_{2,2}$ 会被重复计算，因此需要减去。

洛谷 P1387 最大正方形

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

参考代码

#include <iostream>
#include <vector>

int main() {
  // Input.
  int N1, N2, N3;
  std::cin >> N1 >> N2 >> N3;
  std::vector<std::vector<std::vector<int>>> a(
      N1 + 1, std::vector<std::vector<int>>(N2 + 1, std::vector<int>(N3 + 1)));
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) std::cin >> a[i][j][k];

  // Copy.
  auto ps = a;

  // Prefix-sum for 3rd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  // Prefix-sum for 2nd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  // Prefix-sum for 1st dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];

  // Output.
  for (int i = 1; i <= N1; ++i) {
    for (int j = 1; j <= N2; ++j) {
      for (int k = 1; k <= N3; ++k) {
        std::cout << ps[i][j][k] << ' ';
      }
      std::cout << '\n';
    }
    std::cout << '\n';
  }

  return 0;
}

逐维前缀和

对于一般情况，给定 $k$ 维数组 $A$，要求得其前缀和 $S$，可按每个维度分别累加求和，最终得到 $k$ 维前缀和。

参考实现

#include <iostream>
#include <vector>

int main() {
  // Input.
  int N1, N2, N3;
  std::cin >> N1 >> N2 >> N3;
  std::vector<std::vector<std::vector<int>>> a(
      N1 + 1, std::vector<std::vector<int>>(N2 + 1, std::vector<int>(N3 + 1)));
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) std::cin >> a[i][j][k];

  // Copy.
  auto ps = a;

  // Prefix-sum for 3rd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  // Prefix-sum for 2nd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  // Prefix-sum for 1st dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];

  // Output.
  for (int i = 1; i <= N1; ++i) {
    for (int j = 1; j <= N2; ++j) {
      for (int k = 1; k <= N3; ++k) {
        std::cout << ps[i][j][k] << ' ';
      }
      std::cout << '\n';
    }
    std::cout << '\n';
  }

  return 0;
}

特例：子集和 DP

子集和问题可看作高维前缀和的特例，实现思路与前面类似，时间复杂度为 $O(n2^n)$。

参考实现

#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(1 << n);
  for (int& x : a) std::cin >> x;

  // Copy.
  auto ps = a;
  // Loop over dimensions.
  for (int i = 0; i < n; ++i) {
    // Loop over i-th dimension.
    for (int st = 0; st < (1 << n); ++st) {
      // This condition implies that i-th dimension is 1.
      if ((st >> i) & 1) {
        // ps[... 1 ...] += ps[... 0 ...]. (i-th dimension)
        ps[st] += ps[st ^ (1 << i)];
      }
    }
  }

  for (int x : ps) std::cout << x << ' ';
  return 0;
}

树上前缀和

设 $\textit{sum}_i$ 表示结点 $i$ 到根节点的权值总和，则：

• 若为点权，路径 $x,y$ 上的和为 $\textit{sum}_x + \textit{sum}_y - \textit{sum}_{\textit{lca}} - \textit{sum}_{\textit{fa}_{\textit{lca}}}$。
• 若为边权，则为 $\textit{sum}_x + \textit{sum}_y - 2\cdot\textit{sum}_{lca}$。

差分

解释

差分可视为前缀和的逆运算。定义如下：

$$b_i=\begin{cases}a_i-a_{i-1}, & i \in[2,n] \\ a_1, & i=1\end{cases}$$

性质

• $a_i$ 是 $b_i$ 的前缀和，即 $a_n=\sum\limits_{i=1}^nb_i$。
• 前缀和可转换为

$$\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n(n-i+1)b_i.$$

这种方法常用于对序列内区间的批量修改。

示例

例如，将区间 $[l, r]$ 内每个数加上一个 $k$，可用：

$$b_l \leftarrow b_l + k, \quad b_{r+1} \leftarrow b_{r+1} - k$$

最后再计算一次前缀和，就得到更新后的数组。

C++ 标准库中提供了 std::adjacent_difference 函数，可实现差分操作，定义于 <numeric> 中。

树上差分

树上差分使用类似思想对树上某路径进行区间修改，分为点差分和边差分两种方法。

点差分

例如，对路径 $\delta(s,t)$ 上的所有点加一可采用：

$$\begin{aligned} d_s &\leftarrow d_s+1,\\[6pt] d_{\textit{lca}} &\leftarrow d_{\textit{lca}}-1,\\[6pt] d_t &\leftarrow d_t+1,\\[6pt] d_{f(\textit{lca})} &\leftarrow d_{f(\textit{lca})}-1. \end{aligned}$$

边差分

对路径中边的加权操作则采用：

$$\begin{aligned} d_s &\leftarrow d_s+1,\\[6pt] d_t &\leftarrow d_t+1,\\[6pt] d_{\textit{lca}} &\leftarrow d_{\textit{lca}}-2. \end{aligned}$$

例题

洛谷 3128 最大流

FJ 给他的牛棚的 $N(2 \le N \le 50,000)$ 个隔间之间安装了 $N-1$ 根管道，所有隔间均连通。有 $K(1 \le K \le 100,000)$ 条运输牛奶路线，每条路线会给途径的隔间增加一个单位压力，求压力最大的隔间压力。

解题思路

对每条运输路径采用树上差分，将路径上所有点加一，然后通过 DFS 回溯求和最终得到各个点的压力。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

constexpr int MAXN = 50010;

struct node {
  int to, next;
} edge[MAXN << 1];

int fa[MAXN][30], head[MAXN << 1];
int power[MAXN];
int depth[MAXN], lg[MAXN];
int n, k, ans = 0, tot = 0;

void add(int x, int y) {  // 加边
  edge[++tot].to = y;
  edge[tot].next = head[x];
  head[x] = tot;
}

void dfs(int now, int father) {  // dfs求最大压力
  fa[now][0] = father;
  depth[now] = depth[father] + 1;
  for (int i = 1; i <= lg[depth[now]]; ++i)
    fa[now][i] = fa[fa[now][i - 1]][i - 1];
  for (int i = head[now]; i; i = edge[i].next)
    if (edge[i].to != father) dfs(edge[i].to, now);
}

int lca(int x, int y) {  // 求LCA，最近公共祖先
  if (depth[x] < depth[y]) swap(x, y);
  while (depth[x] > depth[y]) x = fa[x][lg[depth[x] - depth[y]] - 1];
  if (x == y) return x;
  for (int k = lg[depth[x]] - 1; k >= 0; k--) {
    if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
  }
  return fa[x][0];
}

// 用dfs求最大压力，回溯时将子树的权值加上
void get_ans(int u, int father) {
  for (int i = head[u]; i; i = edge[i].next) {
    int to = edge[i].to;
    if (to == father) continue;
    get_ans(to, u);
    power[u] += power[to];
  }
  ans = max(ans, power[u]);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  int x, y;
  for (int i = 1; i <= n; i++) {
    lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
  }
  for (int i = 1; i <= n - 1; i++) {  // 建图
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  int s, t;
  for (int i = 1; i <= k; i++) {
    cin >> s >> t;
    int ancestor = lca(s, t);
    // 树上差分
    power[s]++;
    power[t]++;
    power[ancestor]--;
    power[fa[ancestor][0]]--;
  }
  get_ans(1, 0);
  cout << ans << '\n';
  return 0;
}

习题

前缀和：

• 洛谷 B3612【深进 1. 例 1】求区间和
• 洛谷 U69096 前缀和的逆
• AtCoder joi2007ho_a 最大の和
• 「USACO16JAN」Subsequences Summing to Sevens
• 「USACO05JAN」Moo Volume S

---

二维/多维前缀和：

• HDU 6514 Monitor
• 洛谷 P1387 最大正方形
• 「HNOI2003」激光炸弹
• CF 165E Compatible Numbers
• CF 383E Vowels
• ARC 100C Or Plus Max

---

树上前缀和：

• LOJ 10134.Dis
• LOJ 2491. 求和

---

差分：

• 树状数组 3：区间修改，区间查询
• P3397 地毯
• 「Poetize6」IncDec Sequence

---

树上差分：

• 洛谷 3128 最大流
• JLOI2014 松鼠的新家
• NOIP2015 运输计划
• NOIP2016天天爱跑步

---

参考资料与注释

Footnotes

1. 南海区青少年信息学奥林匹克内部训练教材 ↩